package DynamicProgramming;

import java.util.Arrays;

public class backpack_01 {

    /**
     * Backpack.
     *
     * @param maxWeight the max weight  背包最大负重
     * @param value     the value   物品对应价值
     * @param weight    the weight  物品对应重量
     */
    public static void backpack(int maxWeight, int[] value, int[] weight){
        int len = value.length;  //总物品数量
        //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
        int[][] dp = new int[len][maxWeight+1];
        //初始化,当最大负重为0时,最大价值都为0
        for (int i = 0; i < len; i++) {
            dp[i][0] = 0;
        }
        //初始化，当只放第一件物品时，所以背包负重大于物品重量才能放入
        for (int i = weight[0]; i <= maxWeight; i++) {
            dp[0][i] = value[0];
        }
        /**
         * 某一时刻状态，dp[i][j]的值表示当前能放入的最大价值
         * 1.当i的重量超过了负重j时
         * 其取决于dp[i-1][j]，此时表示，不放入i时的最大价值,
         * 2.若物品i的重量小于负重j时
         * dp[i-1][j-weight[i]] 表示不放入i时的最大价值，
         * 放入i此时价值变为dp[i-1][j-weight[i]]+value[i]
         * dp[i-1][j] 此时表示为不放入i的最大价值
         * 此时最大价值取决于Math.max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j])
         * */

        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 1; i < len; i++) {
            for (int j = 0; j <= maxWeight; j++) {
                if(weight[i] > j ){
                    //表示当i的重量超过了负重j时，放不进去i，最大价值取决于只放i-1最大价值
                    dp[i][j] = dp[i-1][j];
                }else{
                    //能放进去取决于两个状态
                    dp[i][j] = Math.max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j]);
                }
            }
        }

        System.out.println("二维动规");
        for (int i = 0; i < len; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
    }

    public static void backpack1(int maxWeight, int[] value, int[] weight){
        /**
         * 滚动数组做动规
         * */
        int len = value.length;  //总物品数量
        int[] dp = new int[maxWeight+1];
        for (int i = 0; i < len; i++) {
            for (int j = maxWeight; j >= weight[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j-weight[i]] + value[i]);
            }
        }
        System.out.println("滚动数组:"+ Arrays.toString(dp));
    }

    public static void main(String[] args) {
        backpack(4,new int[]{15,20,30}, new int[]{1,3,4});
        backpack1(4,new int[]{15,20,30}, new int[]{1,3,4});
    }
}
